package leetcode_day._2021._202104._0110;

/**
 * @author yzh
 * @date 2021/4/6 20:04
 * 删除有序数组中的重复项 II
 * 思路：
 *   把重复的数字编程最小或最大的，两次循环
 *   设置两个数 a b，a 表示如果当前数和 a 相同，那么 b 加 1
 *   b 超过 2 的时候，就把重复的数置为最大或最小
 *   然后再用双指针改变数组
 *   当没有遇到最大值时，两个指针同时移动，遇到最大值时，一个指针不移动
 *  双指针法
 *    两个指针 a = b = 2；
 *    如果 nums[a - 2] != nums[b], nums[a] = nums[b]
 */
public class _06_80 {
    public static void main(String[] args) {
        int[] nums = new int[]{0,0,1,1,1,1,2,3,3};
        System.out.println(new _06_80().removeDuplicates(nums));
    }

    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) return nums.length;
        int a = nums[0], b = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (a == nums[i]) {
                ++b;
                if (b > 2) nums[i] = Integer.MAX_VALUE;
            } else {
                a = nums[i];
                b = 1;
            }
        }
        int left = 0, right = 0;
        for (int i = 0; i < nums.length; i++) {
            nums[left] = nums[right];
            ++right;
            if (nums[i] != Integer.MAX_VALUE) {
                ++left;
                ++ans;
            }
        }
        return ans;
    }

    public int removeDuplicates_perfect(int[] nums) {
        if (nums.length <= 2) return nums.length;
        int a = 2, b = 2;
        while (b < nums.length) {
            if (nums[a - 2] != nums[b]) { // 如果 nums[b] 和 nums[a - 2] 相同，表示 b 指向的数不能被放进结果数组中
                nums[a] = nums[b];
                ++a;
            }
            ++b;
        }
        return a;
    }
}
